import java.util.ArrayList;
import java.util.List;

public class MaximumClique {
    // 存储最大团的顶点集合（索引从0开始）
    private List<Integer> bestClique = new ArrayList<>();
    // 图的邻接矩阵（graph[i][j] = 1 表示顶点i和j相连）
    private int[][] graph;
    // 图的顶点数
    private int n;

    public List<Integer> findMaximumClique(int[][] graph) {
        this.graph = graph;
        this.n = graph.length;
        // 初始候选集：所有顶点（按顺序排列，避免重复搜索）
        List<Integer> initialCandidates = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            initialCandidates.add(i);
        }
        // 回溯搜索
        backtrack(new ArrayList<>(), initialCandidates);
        return bestClique;
    }

    /**
     * 回溯函数：扩展当前团
     * @param currentClique 当前已形成的团
     * @param candidates 候选顶点集（可能加入当前团的顶点）
     */
    private void backtrack(List<Integer> currentClique, List<Integer> candidates) {
        // 剪枝：当前团 + 候选集大小 ≤ 现有最大团，无需继续
        if (currentClique.size() + candidates.size() <= bestClique.size()) {
            return;
        }

        // 候选集为空，更新最大团
        if (candidates.isEmpty()) {
            if (currentClique.size() > bestClique.size()) {
                bestClique = new ArrayList<>(currentClique);
            }
            return;
        }

        // 遍历候选顶点，尝试加入当前团
        for (int i = 0; i < candidates.size(); i++) {
            int v = candidates.get(i);
            // 检查v是否与当前团中所有顶点相连（保证团的完全性）
            boolean isValid = true;
            for (int u : currentClique) {
                if (graph[v][u] != 1) {
                    isValid = false;
                    break;
                }
            }
            if (!isValid) {
                continue;
            }

            // 新候选集：候选集中在v之后，且与v相连的顶点（避免重复搜索）
            List<Integer> newCandidates = new ArrayList<>();
            for (int j = i + 1; j < candidates.size(); j++) {
                int u = candidates.get(j);
                if (graph[v][u] == 1) {
                    newCandidates.add(u);
                }
            }

            // 选择：将v加入当前团
            currentClique.add(v);
            // 递归：扩展团
            backtrack(currentClique, newCandidates);
            // 回溯：撤销选择
            currentClique.remove(currentClique.size() - 1);
        }
    }

    // 测试用例
    public static void main(String[] args) {
        MaximumClique mc = new MaximumClique();
        // 无向图邻接矩阵（5个顶点）
        int[][] graph = {
                {0, 1, 1, 0, 1},
                {1, 0, 1, 1, 0},
                {1, 1, 0, 1, 1},
                {0, 1, 1, 0, 1},
                {1, 0, 1, 1, 0}
        };
        List<Integer> maxClique = mc.findMaximumClique(graph);
        System.out.println("最大团的顶点集合（索引从0开始）：" + maxClique);
        System.out.println("最大团大小：" + maxClique.size()); // 预期输出3（例如[0,1,2]）
    }
}